The invention concerns the processing of video data for recording on a disk. Video data typically consists of a succession of video frames, each frame consisting of (in the case of NTSC video) 640 columns and 480 rows of picture elements (pixels). Typically, each pixel consists of an eight-bit byte representing the intensity value of the pixel. Video data typically is generated at the rate of 30 frames per second (in the case of NTSC video). In the case of color video, each image consists of three different channels, one channel for each of three primary colors (e.g., red, green and blue). From the foregoing, the data rate of digital color video data is calculated to be about 27 megabytes per second.
Storing video data as it is generated at 30 frames per second is difficult, since the average writing speed of a typical disk is near a range from 10 to 14 megabytes per second, or about half the video data rate. The problem is how to write video data at 27 megabytes per second onto a disk that can be written no faster than half that rate. This problem is solved by either compressing the video data by a factor of two prior to writing to the disk or by sharing the data writing operation among several disks of a disk array. The main disadvantage of compressing the video data by a factor of two is that data compression techniques capable of such a high compression ratio tend to incapable of handling high incoming data rates in real time and, in addition, many such compression techniques are lossy. The main disadvantage of using a disk array is high expense. The present invention is directed to compressing incoming video data at a very high data rate (e.g., 27 megabytes per second) with a compression ratio of about two or more with no loss of image quality.
A conventional lossless video compression process is incapable of handling high speed incoming video data in real time because such a lossless video compression process is typically complex, requiring a relatively large number of computational steps for each pixel. Lossy compression may tend to be simpler in some cases (but not necessarily all cases) because they can employ a smaller number of computational steps for each pixel. The problem is how to perform lossless video compression at high incoming data rates. The problem with a complex lossless compression process at high incoming data rates can be understood with reference to the diagram of FIG. 1A, illustrating the architecture of a typical microprocessor 1. In FIG. 1A, a common data bus 10 is shared by a high speed working memory or random access memory (RAM) 15 and an arithmetic logic unit (ALU) 20. A controller 25 controls the bus 10, the RAM 15 and the ALU 20 to execute successive instructions of a program (stored in the RAM 15, for example) implementing a compression process. For this purpose, incoming uncompressed video data from a camera or VCR 30 is supplied to the bus 10 at an incoming port 35, and compressed video data generated by the process is output on the bus 10 to a disk storage or write device 40 via an outgoing port 45.
Access to the bus by the incoming and outgoing data ports 35, 45 is controlled by the controller 25. Unlike conventional approaches of the prior art, the present invention seeks to store video data from the camera 30 on the disk storage 35 in real time without buffering the video data. In such a case, the compression process performed by the microprocessor 1 must provide a balance between the high data rate of the incoming video data from the camera (e.g., 27 megabytes per second) and the lower data rate at which the disk storage can write data (e.g., less than 10-14 megabytes per second). Specifically, the compression rate of the compression process performed by the microprocessor 1 must be at least as great as the ratio between the incoming video data rate and the write speed of the disk storage 40.
The main problem is that a lossless compression process has too many instructions or operations to perform for each video pixel for the microprocessor to perform at 27 megabytes per second. The reason is that for each arithmetic operation or instruction performed by the ALU 20, a set of intermediate computational results are obtained which must be stored in the RAM 15 to await the computation of other intermediate results in accordance with other instructions or operations, with which they are to be combined in a yet later operation. Since the data bus 10 is shared by the RAM 15 and ALU 20, it limits forces the microprocessor 1 to wait as each intermediate instruction is executed for the results from the ALU 15 to be stored via the bus 10 in the RAM 15 and other results fetched from the RAM 15 via the bus 10 to the ALU 20 for use by the next instruction or operation. Such waiting is necessary to avoid conflicting use of the bus 10, but limits the rate at which the succession of instructions representing the compression process can be performed. As the rate of the incoming (uncompressed) video data is increased, a point is reached at which the processing of the previous video pixel data is still unfinished as the next video pixel data arrives from the camera 30. This occurs well below the real time video data rate of a typical color video camera (27 megabytes per second). One way around this problem is to reduce the number of arithmetic operations performed by the compression process for each video pixel. However, such a reduction leads to a lossy compression process in which image quality of the compressed video data is compromised. In summary, the more complicated compression algorithm will involve more processing steps and each processing step requires getting data from the RAM to and from the ALU or crossing the system bus several times. Since the system bus has limited bandwidth, this can create the processing bottle neck so that the system can not handle the real time data stream.
FIG. 1B illustrates one of the first steps in a standard video compression process, which is to divide each frame 100 of a video image into plural blocks 110 (step 210 of FIG. 2). Then, each block 110 is compressed in a succession of steps, the first of which is to perform a discrete cosine transform on each block (step 220 of FIG. 2). The result is a transformed block consisting of an array of discrete cosine transform coefficients, as illustrated in FIG. 3. These coefficients are encoded using a minimum length encoding scheme, such as a Huffman code (step 230 of FIG. 2). Run length encoding may also be employed (step 240 of FIG. 2). In some video data compressors, the compression ratio is increased by discarding the higher order discrete cosine transform coefficients, namely those on the right side of the diagonal imaginary line of FIG. 3. The remaining coefficients are further quantized to reduce its range. These higher order discrete cosine transform coefficients represent the higher spatial frequencies in the image, corresponding to fine detail features of the image. The discrete cosine transform tends to reduce image quality obtained upon de-compressing the compressed video data, particularly where the higher order discrete cosine transform coefficients are discarded to enhance compression ratio. In addition, blocking artifacts attributable to the division of the video frame into the plural blocks of FIG. 1 and discarding of higher order terms represent a further loss in image quality. However, such trade-offs have been necessary in order to achieve a high compression ratio (such a compression ratio of two or more). Such a reduction of image quality in the video compression process is referred to as lossy video compression.
Heretofore, lossless video compression at a sufficiently high compression rate to balance or compensate in real time for the difference in the data rates of the incoming video signal and the maximum writing speed of a disk storage medium has been unknown. This has presented a fundamental limitation in applications such as forensic image processing, where every image detail must be preserved during image processing. With such a requirement, disk recording of a 30 frame per second video image for forensic purposes, for example, could not be accomplished without use of expensive disk arrays. Therefore, there has been a need for a lossless video compression process having a high compression ratio (e.g., a compression ratio of about two or more).